home *** CD-ROM | disk | FTP | other *** search
/ Amiga Tools 5 / Amiga Tools 5.iso / tools / developer-tools / andere sprachen / perl5 / perl5.002 / ext / sdbm_file / sdbm / sdbm.c < prev    next >
Encoding:
C/C++ Source or Header  |  1996-01-23  |  10.8 KB  |  524 lines
  1. /*
  2.  * sdbm - ndbm work-alike hashed database library
  3.  * based on Per-Aake Larson's Dynamic Hashing algorithms. BIT 18 (1978).
  4.  * author: oz@nexus.yorku.ca
  5.  * status: public domain.
  6.  *
  7.  * core routines
  8.  */
  9.  
  10. #ifndef lint
  11. static char rcsid[] = "$Id: sdbm.c,v 1.16 90/12/13 13:01:31 oz Exp $";
  12. #endif
  13.  
  14. #include "config.h"
  15. #include "sdbm.h"
  16. #include "tune.h"
  17. #include "pair.h"
  18.  
  19. #ifdef I_FCNTL
  20. # include <fcntl.h>
  21. #endif
  22. #ifdef I_SYS_FILE
  23. # include <sys/file.h>
  24. #endif
  25.  
  26. #ifdef I_STRING
  27. # include <string.h>
  28. #else
  29. # include <strings.h>
  30. #endif
  31.  
  32. /*
  33.  * externals
  34.  */
  35. #ifndef sun
  36. extern int errno;
  37. #endif
  38.  
  39. extern Malloc_t malloc proto((MEM_SIZE));
  40. extern Free_t free proto((Malloc_t));
  41. extern Off_t lseek();
  42.  
  43. /*
  44.  * forward
  45.  */
  46. static int getdbit proto((DBM *, long));
  47. static int setdbit proto((DBM *, long));
  48. static int getpage proto((DBM *, long));
  49. static datum getnext proto((DBM *));
  50. static int makroom proto((DBM *, long, int));
  51.  
  52. /*
  53.  * useful macros
  54.  */
  55. #define bad(x)        ((x).dptr == NULL || (x).dsize < 0)
  56. #define exhash(item)    sdbm_hash((item).dptr, (item).dsize)
  57. #define ioerr(db)    ((db)->flags |= DBM_IOERR)
  58.  
  59. #define OFF_PAG(off)    (long) (off) * PBLKSIZ
  60. #define OFF_DIR(off)    (long) (off) * DBLKSIZ
  61.  
  62. static long masks[] = {
  63.     000000000000, 000000000001, 000000000003, 000000000007,
  64.     000000000017, 000000000037, 000000000077, 000000000177,
  65.     000000000377, 000000000777, 000000001777, 000000003777,
  66.     000000007777, 000000017777, 000000037777, 000000077777,
  67.     000000177777, 000000377777, 000000777777, 000001777777,
  68.     000003777777, 000007777777, 000017777777, 000037777777,
  69.     000077777777, 000177777777, 000377777777, 000777777777,
  70.     001777777777, 003777777777, 007777777777, 017777777777
  71. };
  72.  
  73. datum nullitem = {NULL, 0};
  74.  
  75. DBM *
  76. sdbm_open(file, flags, mode)
  77. register char *file;
  78. register int flags;
  79. register int mode;
  80. {
  81.     register DBM *db;
  82.     register char *dirname;
  83.     register char *pagname;
  84.     register int n;
  85.  
  86.     if (file == NULL || !*file)
  87.         return errno = EINVAL, (DBM *) NULL;
  88. /*
  89.  * need space for two seperate filenames
  90.  */
  91.     n = strlen(file) * 2 + strlen(DIRFEXT) + strlen(PAGFEXT) + 2;
  92.  
  93.     if ((dirname = malloc((unsigned) n)) == NULL)
  94.         return errno = ENOMEM, (DBM *) NULL;
  95. /*
  96.  * build the file names
  97.  */
  98.     dirname = strcat(strcpy(dirname, file), DIRFEXT);
  99.     pagname = strcpy(dirname + strlen(dirname) + 1, file);
  100.     pagname = strcat(pagname, PAGFEXT);
  101.  
  102.     db = sdbm_prep(dirname, pagname, flags, mode);
  103.     free((char *) dirname);
  104.     return db;
  105. }
  106.  
  107. DBM *
  108. sdbm_prep(dirname, pagname, flags, mode)
  109. char *dirname;
  110. char *pagname;
  111. int flags;
  112. int mode;
  113. {
  114.     register DBM *db;
  115.     struct stat dstat;
  116.  
  117.     if ((db = (DBM *) malloc(sizeof(DBM))) == NULL)
  118.         return errno = ENOMEM, (DBM *) NULL;
  119.  
  120.         db->flags = 0;
  121.         db->hmask = 0;
  122.         db->blkptr = 0;
  123.         db->keyptr = 0;
  124. /*
  125.  * adjust user flags so that WRONLY becomes RDWR, 
  126.  * as required by this package. Also set our internal
  127.  * flag for RDONLY if needed.
  128.  */
  129.     if (flags & O_WRONLY)
  130.         flags = (flags & ~O_WRONLY) | O_RDWR;
  131.  
  132.     else if ((flags & 03) == O_RDONLY)
  133.         db->flags = DBM_RDONLY;
  134. /*
  135.  * open the files in sequence, and stat the dirfile.
  136.  * If we fail anywhere, undo everything, return NULL.
  137.  */
  138. #    ifdef OS2
  139.     flags |= O_BINARY;
  140. #    endif
  141.     if ((db->pagf = open(pagname, flags, mode)) > -1) {
  142.         if ((db->dirf = open(dirname, flags, mode)) > -1) {
  143. /*
  144.  * need the dirfile size to establish max bit number.
  145.  */
  146.             if (fstat(db->dirf, &dstat) == 0) {
  147. /*
  148.  * zero size: either a fresh database, or one with a single,
  149.  * unsplit data page: dirpage is all zeros.
  150.  */
  151.                 db->dirbno = (!dstat.st_size) ? 0 : -1;
  152.                 db->pagbno = -1;
  153.                 db->maxbno = dstat.st_size * BYTESIZ;
  154.  
  155.                 (void) memset(db->pagbuf, 0, PBLKSIZ);
  156.                 (void) memset(db->dirbuf, 0, DBLKSIZ);
  157.             /*
  158.              * success
  159.              */
  160.                 return db;
  161.             }
  162.             (void) close(db->dirf);
  163.         }
  164.         (void) close(db->pagf);
  165.     }
  166.     free((char *) db);
  167.     return (DBM *) NULL;
  168. }
  169.  
  170. void
  171. sdbm_close(db)
  172. register DBM *db;
  173. {
  174.     if (db == NULL)
  175.         errno = EINVAL;
  176.     else {
  177.         (void) close(db->dirf);
  178.         (void) close(db->pagf);
  179.         free((char *) db);
  180.     }
  181. }
  182.  
  183. datum
  184. sdbm_fetch(db, key)
  185. register DBM *db;
  186. datum key;
  187. {
  188.     if (db == NULL || bad(key))
  189.         return errno = EINVAL, nullitem;
  190.  
  191.     if (getpage(db, exhash(key)))
  192.         return getpair(db->pagbuf, key);
  193.  
  194.     return ioerr(db), nullitem;
  195. }
  196.  
  197. int
  198. sdbm_delete(db, key)
  199. register DBM *db;
  200. datum key;
  201. {
  202.     if (db == NULL || bad(key))
  203.         return errno = EINVAL, -1;
  204.     if (sdbm_rdonly(db))
  205.         return errno = EPERM, -1;
  206.  
  207.     if (getpage(db, exhash(key))) {
  208.         if (!delpair(db->pagbuf, key))
  209.             return -1;
  210. /*
  211.  * update the page file
  212.  */
  213.         if (lseek(db->pagf, OFF_PAG(db->pagbno), SEEK_SET) < 0
  214.             || write(db->pagf, db->pagbuf, PBLKSIZ) < 0)
  215.             return ioerr(db), -1;
  216.  
  217.         return 0;
  218.     }
  219.  
  220.     return ioerr(db), -1;
  221. }
  222.  
  223. int
  224. sdbm_store(db, key, val, flags)
  225. register DBM *db;
  226. datum key;
  227. datum val;
  228. int flags;
  229. {
  230.     int need;
  231.     register long hash;
  232.  
  233.     if (db == NULL || bad(key))
  234.         return errno = EINVAL, -1;
  235.     if (sdbm_rdonly(db))
  236.         return errno = EPERM, -1;
  237.  
  238.     need = key.dsize + val.dsize;
  239. /*
  240.  * is the pair too big (or too small) for this database ??
  241.  */
  242.     if (need < 0 || need > PAIRMAX)
  243.         return errno = EINVAL, -1;
  244.  
  245.     if (getpage(db, (hash = exhash(key)))) {
  246. /*
  247.  * if we need to replace, delete the key/data pair
  248.  * first. If it is not there, ignore.
  249.  */
  250.         if (flags == DBM_REPLACE)
  251.             (void) delpair(db->pagbuf, key);
  252. #ifdef SEEDUPS
  253.         else if (duppair(db->pagbuf, key))
  254.             return 1;
  255. #endif
  256. /*
  257.  * if we do not have enough room, we have to split.
  258.  */
  259.         if (!fitpair(db->pagbuf, need))
  260.             if (!makroom(db, hash, need))
  261.                 return ioerr(db), -1;
  262. /*
  263.  * we have enough room or split is successful. insert the key,
  264.  * and update the page file.
  265.  */
  266.         (void) putpair(db->pagbuf, key, val);
  267.  
  268.         if (lseek(db->pagf, OFF_PAG(db->pagbno), SEEK_SET) < 0
  269.             || write(db->pagf, db->pagbuf, PBLKSIZ) < 0)
  270.             return ioerr(db), -1;
  271.     /*
  272.      * success
  273.      */
  274.         return 0;
  275.     }
  276.  
  277.     return ioerr(db), -1;
  278. }
  279.  
  280. /*
  281.  * makroom - make room by splitting the overfull page
  282.  * this routine will attempt to make room for SPLTMAX times before
  283.  * giving up.
  284.  */
  285. static int
  286. makroom(db, hash, need)
  287. register DBM *db;
  288. long hash;
  289. int need;
  290. {
  291.     long newp;
  292.     char twin[PBLKSIZ];
  293.     char *pag = db->pagbuf;
  294.     char *new = twin;
  295.     register int smax = SPLTMAX;
  296.  
  297.     do {
  298. /*
  299.  * split the current page
  300.  */
  301.         (void) splpage(pag, new, db->hmask + 1);
  302. /*
  303.  * address of the new page
  304.  */
  305.         newp = (hash & db->hmask) | (db->hmask + 1);
  306.  
  307. /*
  308.  * write delay, read avoidence/cache shuffle:
  309.  * select the page for incoming pair: if key is to go to the new page,
  310.  * write out the previous one, and copy the new one over, thus making
  311.  * it the current page. If not, simply write the new page, and we are
  312.  * still looking at the page of interest. current page is not updated
  313.  * here, as sdbm_store will do so, after it inserts the incoming pair.
  314.  */
  315.         if (hash & (db->hmask + 1)) {
  316.             if (lseek(db->pagf, OFF_PAG(db->pagbno), SEEK_SET) < 0
  317.                 || write(db->pagf, db->pagbuf, PBLKSIZ) < 0)
  318.                 return 0;
  319.             db->pagbno = newp;
  320.             (void) memcpy(pag, new, PBLKSIZ);
  321.         }
  322.         else if (lseek(db->pagf, OFF_PAG(newp), SEEK_SET) < 0
  323.              || write(db->pagf, new, PBLKSIZ) < 0)
  324.             return 0;
  325.  
  326.         if (!setdbit(db, db->curbit))
  327.             return 0;
  328. /*
  329.  * see if we have enough room now
  330.  */
  331.         if (fitpair(pag, need))
  332.             return 1;
  333. /*
  334.  * try again... update curbit and hmask as getpage would have
  335.  * done. because of our update of the current page, we do not
  336.  * need to read in anything. BUT we have to write the current
  337.  * [deferred] page out, as the window of failure is too great.
  338.  */
  339.         db->curbit = 2 * db->curbit +
  340.             ((hash & (db->hmask + 1)) ? 2 : 1);
  341.         db->hmask |= db->hmask + 1;
  342.  
  343.         if (lseek(db->pagf, OFF_PAG(db->pagbno), SEEK_SET) < 0
  344.             || write(db->pagf, db->pagbuf, PBLKSIZ) < 0)
  345.             return 0;
  346.  
  347.     } while (--smax);
  348. /*
  349.  * if we are here, this is real bad news. After SPLTMAX splits,
  350.  * we still cannot fit the key. say goodnight.
  351.  */
  352. #ifdef BADMESS
  353.     (void) write(2, "sdbm: cannot insert after SPLTMAX attempts.\n", 44);
  354. #endif
  355.     return 0;
  356.  
  357. }
  358.  
  359. /*
  360.  * the following two routines will break if
  361.  * deletions aren't taken into account. (ndbm bug)
  362.  */
  363. datum
  364. sdbm_firstkey(db)
  365. register DBM *db;
  366. {
  367.     if (db == NULL)
  368.         return errno = EINVAL, nullitem;
  369. /*
  370.  * start at page 0
  371.  */
  372.     if (lseek(db->pagf, OFF_PAG(0), SEEK_SET) < 0
  373.         || read(db->pagf, db->pagbuf, PBLKSIZ) < 0)
  374.         return ioerr(db), nullitem;
  375.     db->pagbno = 0;
  376.     db->blkptr = 0;
  377.     db->keyptr = 0;
  378.  
  379.     return getnext(db);
  380. }
  381.  
  382. datum
  383. sdbm_nextkey(db)
  384. register DBM *db;
  385. {
  386.     if (db == NULL)
  387.         return errno = EINVAL, nullitem;
  388.     return getnext(db);
  389. }
  390.  
  391. /*
  392.  * all important binary trie traversal
  393.  */
  394. static int
  395. getpage(db, hash)
  396. register DBM *db;
  397. register long hash;
  398. {
  399.     register int hbit;
  400.     register long dbit;
  401.     register long pagb;
  402.  
  403.     dbit = 0;
  404.     hbit = 0;
  405.     while (dbit < db->maxbno && getdbit(db, dbit))
  406.         dbit = 2 * dbit + ((hash & (1 << hbit++)) ? 2 : 1);
  407.  
  408.     debug(("dbit: %d...", dbit));
  409.  
  410.     db->curbit = dbit;
  411.     db->hmask = masks[hbit];
  412.  
  413.     pagb = hash & db->hmask;
  414. /*
  415.  * see if the block we need is already in memory.
  416.  * note: this lookaside cache has about 10% hit rate.
  417.  */
  418.     if (pagb != db->pagbno) { 
  419. /*
  420.  * note: here, we assume a "hole" is read as 0s.
  421.  * if not, must zero pagbuf first.
  422.  */
  423.         if (lseek(db->pagf, OFF_PAG(pagb), SEEK_SET) < 0
  424.             || read(db->pagf, db->pagbuf, PBLKSIZ) < 0)
  425.             return 0;
  426.         if (!chkpage(db->pagbuf))
  427.             return 0;
  428.         db->pagbno = pagb;
  429.  
  430.         debug(("pag read: %d\n", pagb));
  431.     }
  432.     return 1;
  433. }
  434.  
  435. static int
  436. getdbit(db, dbit)
  437. register DBM *db;
  438. register long dbit;
  439. {
  440.     register long c;
  441.     register long dirb;
  442.  
  443.     c = dbit / BYTESIZ;
  444.     dirb = c / DBLKSIZ;
  445.  
  446.     if (dirb != db->dirbno) {
  447.         if (lseek(db->dirf, OFF_DIR(dirb), SEEK_SET) < 0
  448.             || read(db->dirf, db->dirbuf, DBLKSIZ) < 0)
  449.             return 0;
  450.         db->dirbno = dirb;
  451.  
  452.         debug(("dir read: %d\n", dirb));
  453.     }
  454.  
  455.     return db->dirbuf[c % DBLKSIZ] & (1 << dbit % BYTESIZ);
  456. }
  457.  
  458. static int
  459. setdbit(db, dbit)
  460. register DBM *db;
  461. register long dbit;
  462. {
  463.     register long c;
  464.     register long dirb;
  465.  
  466.     c = dbit / BYTESIZ;
  467.     dirb = c / DBLKSIZ;
  468.  
  469.     if (dirb != db->dirbno) {
  470.         if (lseek(db->dirf, OFF_DIR(dirb), SEEK_SET) < 0
  471.             || read(db->dirf, db->dirbuf, DBLKSIZ) < 0)
  472.             return 0;
  473.         db->dirbno = dirb;
  474.  
  475.         debug(("dir read: %d\n", dirb));
  476.     }
  477.  
  478.     db->dirbuf[c % DBLKSIZ] |= (1 << dbit % BYTESIZ);
  479.  
  480.     if (dbit >= db->maxbno)
  481.         db->maxbno += DBLKSIZ * BYTESIZ;
  482.  
  483.     if (lseek(db->dirf, OFF_DIR(dirb), SEEK_SET) < 0
  484.         || write(db->dirf, db->dirbuf, DBLKSIZ) < 0)
  485.         return 0;
  486.  
  487.     return 1;
  488. }
  489.  
  490. /*
  491.  * getnext - get the next key in the page, and if done with
  492.  * the page, try the next page in sequence
  493.  */
  494. static datum
  495. getnext(db)
  496. register DBM *db;
  497. {
  498.     datum key;
  499.  
  500.     for (;;) {
  501.         db->keyptr++;
  502.         key = getnkey(db->pagbuf, db->keyptr);
  503.         if (key.dptr != NULL)
  504.             return key;
  505. /*
  506.  * we either run out, or there is nothing on this page..
  507.  * try the next one... If we lost our position on the
  508.  * file, we will have to seek.
  509.  */
  510.         db->keyptr = 0;
  511.         if (db->pagbno != db->blkptr++)
  512.             if (lseek(db->pagf, OFF_PAG(db->blkptr), SEEK_SET) < 0)
  513.                 break;
  514.         db->pagbno = db->blkptr;
  515.         if (read(db->pagf, db->pagbuf, PBLKSIZ) <= 0)
  516.             break;
  517.         if (!chkpage(db->pagbuf))
  518.             break;
  519.     }
  520.  
  521.     return ioerr(db), nullitem;
  522. }
  523.  
  524.